package org.farms.algo;


import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Random;


public class MaxBomb {

	//testing parameters
	static int gridSize = 100;
	static int population = 100;
	static int maxCell = 50;
	
	static int bombCost = 10;
	static int minOptimizationCriteria = 0;
	static int maxCircleRadius = 19;
	
	static int[][] mainMatrix;
	static int[][] helpMatrix;
	static int[] helpSectorSum;
	
	static int size;
	
	static int[] bestBombCenter=new int[2];
	static int bestBombRadius;
	static double bestRatio = 0;
	static int bestProfit = 0;
	static int bestMinesInside = 0;

	static int tempCurrentRadius ;
	static int[] tempBombCenter = new int[2];
	static double tempRatio;
	static int tempProfit;
	static int tempMiddleLine;
	//additional measures
	static int tempMinesInside;
	static int tempChickensInside;
	static double tempPigsNeededCost;
	static double tempCustomRating;
	
	static int tunnelUpperBorder;
	static int tunnelLowerBorder;
	
	static int[] tempCircleTraverseBorder;
	
	//additional stats
	static int totalProfit;
	static int totalMines;
	
	//can be optimized
	static int[][] mines;
	
	
	public static void main(String[] args) throws FileNotFoundException {

		PrintStream console = System.out;

		File file = new File("D:/Projects/BigBombs/output.txt");
		FileOutputStream fos = new FileOutputStream(file);
		PrintStream ps = new PrintStream(fos);
		System.setOut(ps);
		
		
		int[][] inputMatrix = new int[100][100];
		inputMatrix[4][5] = -1;
		inputMatrix[4][6] = 20;
		inputMatrix[4][4] = 20;
		inputMatrix[11][12] = -1;
		inputMatrix[11][13] = 20;
		inputMatrix[11][11] = 20;
		inputMatrix[22][22] = -1;
		inputMatrix[22][23] = 20;
		inputMatrix[22][21] = 20;
		
		/*
		int[][] inputMatrix = new int[][] {	{1,2,3,4,5,6,7},
													{1,2,3,4,5,6,7},
													{1,2,3,4,5,6,7},
													{1,2,3,-1,5,6,7},
													{1,2,3,4,5,6,7},
													{1,2,3,4,5,6,7},
													{1,2,3,4,5,6,7},
													};

		*/
		//generateMatrix();
		
		long startTime = System.currentTimeMillis();
		
		getBestBomb(inputMatrix);
		
		printMatrixStats();
		
		System.out.println("\nBest bomb is: " + printBestBombStats());
						
		System.setOut(console);
		//Time
		long endTime = System.currentTimeMillis();
		System.out.println("Bomb Exploded in " + (endTime - startTime)/1000.0 + " seconds.");
	}
	
	public static int[] getBestBomb(int[][] inputMatrix)
	{
		mainMatrix = new int[inputMatrix[0].length][inputMatrix[0].length];
		
		for (int i = 0; i < mainMatrix[0].length; i++) {
			for (int j = 0; j < mainMatrix[0].length; j++) {
				mainMatrix[i][j] = inputMatrix[i][j];
			}
		}
		
		initParameters();

		//Main work
		getMaxCircle();
		
		return new int[] {bestBombCenter[0], bestBombCenter[1], bestBombRadius, 
				bestProfit};
	}

	public static void getMaxCircle()
	{	
		//Fill Help Matrixes
		fillHelpMatrix();
		
		//Go over all possible circles and find the best
		traverseMatrix();
	}


	private static void traverseMatrix() 
	{
		for (int i = 0; i < size; i++) {
			//optimization
			if (helpSectorSum[i] <= minOptimizationCriteria)
				continue;
			for (int j = i; j - i <= 2*maxCircleRadius && j<size; j=j+2) 
			{
				//second optimization
				if (i>0 && helpSectorSum[j] - helpSectorSum[i-1] <= minOptimizationCriteria)
					continue;
				
				tunnelUpperBorder = i;
				tunnelLowerBorder = j;
				
				tempRatio = 0;
				
				tempMiddleLine = (tunnelUpperBorder + tunnelLowerBorder)/2;
				
				tempCurrentRadius = tempMiddleLine - tunnelUpperBorder;
				
				if (i==j)
					findBestCircleInLine();
				else
					findBestCircleInTunnel();
			}
			
		}
		
	}


	private static void findBestCircleInLine() {
		
		for (int i = 0; i < size; i++) 
		{
			tempProfit = mainMatrix[tunnelUpperBorder][i];
			tempRatio = tempProfit/10.0;
			tempBombCenter[0] = tunnelUpperBorder;
			tempBombCenter[1] = i;
			//mines added
			tempMinesInside = mines[tunnelUpperBorder][i];
			if (tunnelUpperBorder>0)
			{
				tempMinesInside -= mines[tunnelUpperBorder - 1][i];
			}
			
			checkIfBest();
		}
		
	}


	private static void findBestCircleInTunnel() {

		fillCircleTraverseBorder();
		
		printCircleBorderInTunnel();

		traverseTunnel();
		
	}
	

	//Traverse the tunnel and calculate each circle
	//Can be optimized
	private static void traverseTunnel() 
	{
		int tempSum = 0;
		
		//System.out.println("Circles:");
		
		for (int i = 0; i < size; i++) 
		{
			tempSum = 0;
			//mines added
			tempMinesInside = 0;
			
			//Center column
			tempSum = helpMatrix[tunnelLowerBorder][i];
			tempMinesInside = mines[tunnelLowerBorder][i];
			
			if (tunnelUpperBorder>0)
			{
				tempSum -= helpMatrix[tunnelUpperBorder - 1][i];
				tempMinesInside -= mines[tunnelUpperBorder - 1][i];
			}
			
			//RightHalf
			for (int j = 0; j < tempCurrentRadius && i + 1 + j<size; j++) 
			{
				tempSum += helpMatrix[tunnelLowerBorder - tempCircleTraverseBorder[j]][i+1+j];
				tempMinesInside += mines[tunnelLowerBorder - tempCircleTraverseBorder[j]][i+1+j];
				
				if (tunnelUpperBorder!=0 || tempCircleTraverseBorder[j]>0)
				{
					tempSum -= helpMatrix[tunnelUpperBorder + tempCircleTraverseBorder[j]-1][i+1+j];
					tempMinesInside -= mines[tunnelUpperBorder + tempCircleTraverseBorder[j]-1][i+1+j];
				}
			}
			
			//Left Half
			for (int j = 0; j < tempCurrentRadius && i - 1 - j >= 0; j++) 
			{
				tempSum += helpMatrix[tunnelLowerBorder - tempCircleTraverseBorder[j]][i-1-j];
				tempMinesInside += mines[tunnelLowerBorder - tempCircleTraverseBorder[j]][i-1-j];
				
				if (tunnelUpperBorder!=0 || tempCircleTraverseBorder[j]>0)
				{
					tempSum -= helpMatrix[tunnelUpperBorder + tempCircleTraverseBorder[j]-1][i-1-j];
					tempMinesInside -= mines[tunnelUpperBorder + tempCircleTraverseBorder[j]-1][i-1-j];
				}
			}
			
			tempProfit = tempSum;
			tempRatio = tempProfit/(tempCurrentRadius*10.0 + 10.0);
			tempBombCenter[0] = tempMiddleLine;
			tempBombCenter[1] = i;
			
			//For tests
			//System.out.print(tempSum + " ");
			
			//Check if best
			checkIfBest();
		}
		//System.out.println();
		
	}

	//Choosing the best Circle
	private static void checkIfBest() 
	{
		//Calculating min custom rating
		tempChickensInside = tempProfit - tempMinesInside*6;
		
		tempPigsNeededCost = 7*(tempChickensInside + (tempChickensInside%2==0?1:2))/2.0;
		
		tempCustomRating = tempProfit/tempPigsNeededCost;
		
		//For testing purposes
		//System.out.println("Checking ("+tempBombCenter[0] + "," + tempBombCenter[1]+")->"
		//		+ tempCurrentRadius + ", profit: " + tempProfit + ", Chickens: " + tempChickensInside
		//		+ ", Pigs needed cost: " + tempPigsNeededCost);
		
		//if (tempRatio>=tempCustomRating && tempProfit > bestProfit) 
		if (tempRatio > bestRatio)
		{
			bestRatio = tempRatio;
			bestBombRadius = tempCurrentRadius;
			bestBombCenter[0] = tempBombCenter[0];
			bestBombCenter[1] = tempBombCenter[1];
			bestProfit = tempProfit;
		
			//For testing purposes
			//System.out.println("Best circle is changed -> " + printBestBombStats());
		}
		
	}


	//Create the contour of the circle in the first quadrant
	private static void fillCircleTraverseBorder() 
	{
		int vertical = 0;
		for (int i = 1; i <= tempCurrentRadius; i++) 
		{
			if (isInside(i,vertical))
			{
				tempCircleTraverseBorder[i-1] = vertical;
			}
			else
			{
				tempCircleTraverseBorder[i-1] = ++vertical;
			}
		}
		
	}

	//Check whether a point is within the current circle (pos from the center and vertical from the top)
	private static boolean isInside(int pos, int vertical) 
	{	
		//Just to check whether there is a distance with .000 length
		//System.out.println(Math.sqrt(pos*pos + (tempCurrentRadius-vertical)*(tempCurrentRadius-vertical)));
		
		return Math.sqrt(pos*pos + (tempCurrentRadius-vertical)*(tempCurrentRadius-vertical))
				<= tempCurrentRadius;
	}

	//Dynamic programming at its best
	private static void fillHelpMatrix() 
	{
		int tempSum = 0;
		
		for (int i = 0; i < size; i++) 
		{
			//-1 for mines
			if (mainMatrix[0][i]== -1)
			{
				mainMatrix[0][i]=6;
				mines[0][i] = 1;;
			}
			
			
			helpMatrix[0][i] = mainMatrix[0][i];
			tempSum += helpMatrix[0][i];
		}
		helpSectorSum[0] = tempSum;
		
		
		for (int i = 1; i < size; i++) 
		{
			tempSum = 0;
			for (int j = 0; j < size; j++) 
			{
				//-1 for mines
				mines[i][j] = mines[i-1][j];
				if (mainMatrix[i][j]== -1)
				{
					mainMatrix[i][j]=6;
					++mines[i][j];
				}
				
				helpMatrix[i][j] = helpMatrix[i-1][j] + mainMatrix[i][j];
				
				tempSum += helpMatrix[i][j];
			}
			helpSectorSum[i] = tempSum;
		}
		
		//Calculating the total Profit
		for (int i = 0; i < size; i++) 
		{
			totalProfit += helpMatrix[size-1][i];
			totalMines += mines[size-1][i];
		}
	}

	private static void generateMatrix() 
	{
		mainMatrix = new int[gridSize][gridSize];
		
		Random rand = new Random();
		
		for (int i = 0; i < population; i++) 
		{
			mainMatrix[rand.nextInt(gridSize)][rand.nextInt(gridSize)] = rand.nextInt(maxCell);
		}
		
	}

	private static void printMatrixStats() 
	{
		//Print some Result
		System.out.println("Help Matrix and Line Sums:");
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (i == bestBombCenter[0] && j == bestBombCenter[1])
				{
					System.out.print(" X"+mainMatrix[i][j] );
				}
				else
					System.out.print(String.format("%3d", mainMatrix[i][j]));
			}
			System.out.println();
		}
		
		for (int i = 0; i < helpSectorSum.length; i++) {
			System.out.print(helpSectorSum[i] + ",");
		}
		
		/*
		//Print mines
		System.out.println("mines matrix:");
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
					System.out.print(String.format("%2d", mines[i][j]));
			}
			System.out.println();
		}
		*/
	}

	private static void printCircleBorderInTunnel() 
	{
		//See the border
		System.out.println("The border alignments for " + tunnelUpperBorder +" and "
				+tunnelLowerBorder + ":");
		for (int j2 = 0; j2 < tempCurrentRadius; j2++) {
			System.out.print(tempCircleTraverseBorder[j2] + ", ");
		}
		System.out.println();
	}

	private static String printBestBombStats()
	{
		return String.format("center(" + bestBombCenter[0] + "," + bestBombCenter[1] 
				+ "), radius: " + bestBombRadius + ", ratio: " + bestRatio
				+ ", profit: " + bestProfit);
	}
	
	private static void initParameters() 
	{
		//Necessary definitions
		size = mainMatrix[0].length;
		
		helpMatrix = new int[size][size];
		
		helpSectorSum = new int[size];
		
		tempCircleTraverseBorder = new int[maxCircleRadius];
		
		//mines added
		mines = new int[size][size];
	}
}


